class Solution {
public:
    struct mylist
    {
        mylist(long long val, int i) :_val(val), prev(nullptr), next(nullptr), _i(i)
        {}
        int _i;
        long long _val;
        mylist* prev;
        mylist* next;
    };
    void change(mylist** pcur, long long val, long long& ma, int i)
    {
        mylist* tmp = new mylist(val, i);
        if (val <= (*pcur)->_val)
        {
            (*pcur)->next = tmp;
            tmp->prev = (*pcur);
        }
        else
        {
            while ((*pcur)->_val < val && (*pcur)->_val != ma) (*pcur) = (*pcur)->prev;
            ma = max(ma, val);
            (*pcur)->next = tmp;
            tmp->prev = (*pcur);
        }
        (*pcur) = tmp;
    }
    long long trap(vector<int>& arr) {
        long long left = 0, right = 1, n = arr.size(), sum = 0, ma = arr[0];
        if (n <= 2) return 0;
        mylist* head = new mylist(arr[0], 0);
        mylist* pcur = head;
        for (int i = 1; i < n; i++)
            if (i == n - 1)
                change(&pcur, arr[i], ma, i);
            else if (arr[i] > arr[i - 1] && arr[i] >= arr[i + 1])
                change(&pcur, arr[i], ma, i);
        pcur = head->next;
        int curmin = min(head->_val, pcur->_val);
        for (int i = 1; i < n - 1; i++)
        {
            if (i == pcur->_i) curmin = min(pcur->_val, pcur->next->_val), pcur = pcur->next;
            else sum += (curmin >= arr[i] ? curmin - arr[i] : 0);
        }

        return sum;
    }
};